﻿namespace ContentHolder
{
    public sealed class SingleKeywordXMatcher : IKeywordMatcher
    {
        private readonly ACMatcher _matcher;
        public SingleKeywordXMatcher(IEnumerable<string> keywords)
        {
            Trie trie = new();
            foreach (var element in keywords)
            {
                trie.Insert(element);
            }
            var automaton = new ACAutomaton(trie.Root);

            _matcher = new ACMatcher(automaton);
        }

        public IEnumerable<string> Matching(string source)
        {
            return this._matcher.FindKeywords(source);
        }

        public class ACMatcher
        {
            private ACAutomaton automaton;

            public ACMatcher(ACAutomaton automaton)
            {
                this.automaton = automaton;
            }

            public List<string> FindKeywords(string text)
            {
                List<string> keywords = new List<string>();
                TrieNode? current = automaton.Root;

                if (current == null)
                {
                    return keywords;
                }

                for (int i = 0; i < text.Length; i++)
                {
                    char c = text[i];

                    // 在失败指针链上查找匹配的子节点
                    while (current != automaton.Root && !current!.Children.ContainsKey(c))
                    {
                        current = current.Failure;
                    }

                    if (current.Children.ContainsKey(c))
                    {
                        current = current.Children[c];
                    }

                    // 如果当前节点是关键词的结尾，则添加关键词到结果列表
                    if (current.IsEndOfWord)
                    {
                        string keyword = text.Substring(i - current.Depth + 1, current.Depth);
                        keywords.Add(keyword);
                    }
                }

                return keywords;
            }

            public List<(string, (int, int))> FindCombinKeywords(string text)
            {
                List<(string, (int, int))> keywords = new();
                TrieNode? current = automaton.Root;

                if (current == null)
                {
                    return keywords;
                }

                for (int i = 0; i < text.Length; i++)
                {
                    char c = text[i];

                    // 在失败指针链上查找匹配的子节点
                    while (current != automaton.Root && !current!.Children.ContainsKey(c))
                    {
                        current = current.Failure;
                    }

                    if (current.Children.ContainsKey(c))
                    {
                        current = current.Children[c];
                    }

                    // 如果当前节点是关键词的结尾，则添加关键词到结果列表
                    if (current.IsEndOfWord)
                    {
                        string keyword = text.Substring(i - current.Depth + 1, current.Depth);
                        keywords.Add((keyword, (i - current.Depth + 1, i - current.Depth + 1 + current.Depth)));
                    }
                }

                return keywords;
            }
        }

        public class ACAutomaton
        {
            private TrieNode _root;

            public TrieNode Root => _root;

            public ACAutomaton(TrieNode root)
            {
                this._root = root;
                BuildFailurePointers();
            }

            private void BuildFailurePointers()
            {
                Queue<TrieNode> queue = new Queue<TrieNode>();

                // 设置根节点的失败指针为自身
                _root.Failure = _root;

                // 将根节点的子节点加入队列，并设置其失败指针为根节点
                foreach (TrieNode child in _root.Children.Values)
                {
                    child.Failure = _root;
                    queue.Enqueue(child);
                }

                // 通过BFS遍历每个节点，为其设置失败指针
                while (queue.Count > 0)
                {
                    TrieNode current = queue.Dequeue();

                    foreach (TrieNode child in current.Children.Values)
                    {
                        char c = child.Value;
                        TrieNode? failure = current.Failure;

                        // 在失败指针链上查找匹配的子节点
                        while (failure != null && failure != _root && !failure.Children.ContainsKey(c))
                        {
                            failure = failure.Failure;
                        }

                        if (failure != null && failure.Children.ContainsKey(c))
                        {
                            child.Failure = failure.Children[c];
                        }
                        else
                        {
                            child.Failure = _root;
                        }

                        queue.Enqueue(child);
                    }
                }
            }
        }

        public class TrieNode
        {
            public char Value { get; set; }
            public bool IsEndOfWord { get; set; }
            public Dictionary<char, TrieNode> Children { get; set; }
            public TrieNode? Failure { get; internal set; }
            public int Depth { get; internal set; }

            public TrieNode(char value)
            {
                Value = value;
                IsEndOfWord = false;
                Children = new Dictionary<char, TrieNode>();
                Depth = 0;
            }
        }

        public class Trie
        {
            private TrieNode _root;

            public TrieNode Root => this._root;

            public Trie()
            {
                _root = new TrieNode('\0');
            }

            public void Insert(string word)
            {
                TrieNode current = _root;
                foreach (char c in word)
                {
                    if (!current.Children.ContainsKey(c))
                    {
                        current.Children[c] = new TrieNode(c);
                    }
                    current = current.Children[c];
                }
                current.IsEndOfWord = true;
                CalculateDepth(_root, 0);
            }

            public void CalculateDepth(TrieNode node, int depth)
            {
                foreach (var child in node.Children.Values)
                {
                    child.Depth = depth + 1;
                    CalculateDepth(child, depth + 1);
                }
            }
        }

    }
}
